class Solution {
public:
    void reserve(vector<int>& a, int left, int right)
    {
        while (left < right)
        {
            int tmp = a[left];
            a[left] = a[right];
            a[right] = tmp;
            left++;
            right--;

        }

    }
    vector<int> solve(int n, int m, vector<int>& a) {
        m %= n;
        reserve(a, 0, n - 1);
        reserve(a, 0, m - 1);
        reserve(a, m, n - 1);
        return a;

    }
}; #include <type_traits>
class Solution {
public:

    vector<vector<int> > rotateMatrix(vector<vector<int> >& mat, int n) {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                swap(mat[i][j], mat[j][i]);

            }

        }

        for (int i = 0; i < n; i++)
        {

            for (int j = 0; j < n / 2; j++)
            {
                swap(mat[i][j], mat[i][n - j - 1]);

            }








        }






        return mat;









    }
}; class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>>
     * @return int整型
     */
    int m;
    int n;
    bool used[230][230];
    int solve(vector<vector<char> >& grid) {
        m = grid.size();
        n = grid[0].size();
        int count = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {

                if (grid[i][j] == '1' && used[i][j] == false)
                {
                    count++;
                    dfs(i, j, grid);

                }


            }
        }
        return count;
    }
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };

    void dfs(int x, int y, vector<vector<char> >& grid)
    {

        used[x][y] = true;

        for (int i = 0; i < 4; i++)
        {
            int newx = x + dx[i];
            int newy = y + dy[i];
            if (newx >= 0 && newx < m && newy >= 0 && newy < n && !used[newx][newy] && grid[newx][newy] == '1')
            {

                dfs(newx, newy, grid);

            }

        }


    }
}; class Solution {
public:

    int maxDepth(TreeNode* root) {
        if (root == nullptr)return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);

        return left > right ? left + 1 : right + 1;

    }
}; class Solution {
public:
    void reserve(string& str, int left, int right)
    {
        while (left < right)
        {


            char tmp = str[left];
            str[left] = str[right];
            str[right] = tmp;
            left++;
            right--;

        }


    }

    string solve(string str) {
        reserve(str, 0, str.size() - 1);
        return str;

    }
}; class Solution {
public:

    bool judge(string str) {

        int left = 0;
        int right = str.size() - 1;
        while (left < right)
        {
            if (str[left] != str[right])
            {
                return false;
            }
            left++;
            right--;

        }
        return true;


    }
};
class Solution {
public:
    vector<int>result;
    void  _inorderTraversal(TreeNode* root)
    {
        if (root == nullptr)
        {
            return;
        }
        _inorderTraversal(root->left);
        result.push_back(root->val);
        _inorderTraversal(root->right);

    }
    vector<int> inorderTraversal(TreeNode* root) {


        _inorderTraversal(root);
        return result;

    }
};
class Solution {
public:
    vector<int>result;
    void  _inorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        result.push_back(root->val);
        _inorderTraversal(root->left);

        _inorderTraversal(root->right);

    }
    vector<int> preorderTraversal(TreeNode* root) {


        _inorderTraversal(root);
        return result;

    }
};
class Solution {
public:
    vector<int>result;
    void  _inorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return;
        }

        _inorderTraversal(root->left);

        _inorderTraversal(root->right);
        result.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {


        _inorderTraversal(root);
        return result;

    }
}; class Solution {
public:

    int findKth(vector<int>& a, int n, int K) {
        priority_queue<int, vector<int>, less<int>>st;

        for (auto e : a)
        {
            st.push(e);

        }
        while (K > 1)
        {

            st.pop();
            K--;
            //if(K==0)break;

        }
        return st.top();

    }
};